#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-09 3:22 下午
# @Author  : yangdy
# @File    : 2020-09-09.39.组合总和
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        if not candidates:
            return ans
        cn = len(candidates)

        def dfs(i, n, t, cc):
            if i >= n or t <= 0:
                return
            for j in range(t//candidates[i]+1):
                xx = j*candidates[i]
                if xx == t:
                    ans.append(cc+[candidates[i]]*j)
                elif xx < t:
                    dfs(i+1, n, t-xx, cc+[candidates[i]]*j)
        dfs(0, cn, target, [])

        return ans


questions = [
    ([2, 3, 6, 7], 7),
    ([2, 3, 5], 8),
]

work(questions, lambda q:Solution().combinationSum(q[0], q[1]))
